Smallest range

Time: O(NLogK); Space: O(K); hard

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

Example 1:

Input: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]

Output: [20,24]

Explanation:

  • List 1: [4, 10, 15, 24,26], 24 is in range [20,24].

  • List 2: [0, 9, 12, 20], 20 is in range [20,24].

  • List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3,4]]

Output: [1,1]

Explanation:

  • List 1: [1,2,3,4], 1 is in range [1,1].

Constraints:

  • the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

  • The given list may contain duplicates, so ascending order means >= here.

  • 1 <= k <= 3500

  • -105 <= value of elements <= 105.

[1]:

import heapq

class Solution1(object):
    """
    Time: O(NLogK)
    Space: O(K)
    """
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """
        left, right = float("inf"), float("-inf")
        min_heap = []

        for row in nums:
            left = min(left, row[0])
            right = max(right, row[0])
            it = iter(row)
            heapq.heappush(min_heap, (next(it, None), it))

        result = (left, right)
        while min_heap:
            (val, it) = heapq.heappop(min_heap)
            val = next(it, None)
            if val is None:
                break
            heapq.heappush(min_heap, (val, it))
            left, right = min_heap[0][0], max(right, val)
            if right - left < result[1] - result[0]:
                result = (left, right)

        return result

[5]:

s = Solution1()

nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
assert list(s.smallestRange(nums)) == [20,24]

nums = nums = [[1,2,3,4]]
assert list(s.smallestRange(nums)) == [1,1]